package _mst;

import _object.ListNode;

/**
 * 面试题 02.06. 回文链表
 */
public class T0206 {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        ListNode pre = null, cur = head, nex;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }

        if (fast != null) slow = slow.next;

        while (pre != null) {
            if (slow.val != pre.val) return false;
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }
}
